大意:
你的商店的名字是字符串S,对手的是T。你现在可以交换你自己的字符串中的一对字母使得字典序改变,问你能否在至多进行这种操作一次的前提下使得你自己的商店的名字的字典序严格小于对手的,或是确定无法做到
分析:
我们要做到的目的就是通过交换一对字母使得当前的字典序能变小,实际上我们也不用先来看T的组成,考虑:怎样使得S的字典序最小,然后再来比较跟T谁大;如果已经到了最小的字典序还不能满足条件比对手的字典序更小的话说明无解,反之直接输出答案即可。
现在的问题就是怎样确定是最小的:由于字典序的定义是从前往后顺次匹配的,所以我们只需要优先考虑最靠前的字符是否是当前序列内最小的就可以了,也就是从第一位顺次开始考虑后面是否有一个字符放在这里是更优的,比如“AZAMON”中第一位肯定就是最小的了,没有更换的;但是第二位Z明显后面就有一个更小的'A'替换后更优,所以对于“AZAMON”来说其能得到的最小的就是“AAZMON”。
这启发我们做一个后缀min数组f,即f[i]表示下标i(从i+1开始)之后最小的字符可以是谁,剩下的判断当前位置是否比后面最小的更大就可以了。
代码:https://codeforces.com/contest/1281/submission/73626333
CF1281B 贪心/字符串
- 本文作者: DreamJuice
- 本文链接: https://Dreamfarer.github.io/post/Zt1JFP95G/
- 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
0%
x
感谢您的支持,我会继续努力的!
扫码打赏,你说多少就多少
打开微信扫一扫,即可进行扫码打赏哦